package com.lw.leetcode.dp.b;

/**
 * Created with IntelliJ IDEA.
 * dp
 * 486. 预测赢家
 *
 * @author liw
 * @version 1.0
 * @date 2021/10/8 15:27
 */
public class PredictTheWinner {

    public boolean PredictTheWinner(int[] nums) {
        int length = nums.length;
        int[][] arr = new int[length][length];
        for (int i = length - 1; i >= 0; i--) {
            arr[i][i] = nums[i];
            for (int j = i + 1; j < length; j++) {
                arr[i][j] = Math.max(nums[i] - arr[i + 1][j], nums[j] - arr[i][j - 1]);
            }
        }
        return arr[0][length - 1] >= 0;
    }

}
